package com.example.algorithm.backtracing;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * <p>
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 * <p>
 * 提示：
 * 1 <= n <= 8
 * <p>
 * Related Topics 字符串 动态规划 回溯
 */
public class Leetcode22_GenerateParenthesis {
    public static void main(String[] args) {
        List<String> strs = new Solution().generateParenthesis(3);
        System.out.println(strs.size());
        strs.forEach(e -> System.out.println(e));

    }

    static class Solution {
        /**
         * 回溯法
         * <p>
         * 在任何时刻，都有两种选择：
         * 1.加左括号 。
         * 2.加右括号 。
         * <p>
         * 同时有以下限制：
         * 1. 如果 左括号已经用完了 ，则不能再加左括号了。
         * 2. 如果 已经出现的右括号和左括号一样多 ，则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。
         * <p>
         * 结束条件是：
         * 左右括号都已经用完
         * 结束后的正确性：
         * 左右括号用完以后，一定是正确解。因为
         * 1. 左右括号一样多 ，
         * 2. 每个右括号都一定有与之配对的左括号 。因此一旦结束就可以加入解集（有时也可能出现结束以后不一定是正确解的情况，这时要多一步判断）。
         *
         * @param n
         * @return
         */
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();

            backtrace(res, "", 0, 0, n);

            return res;
        }

        public void backtrace(List<String> res, String str, int left, int right, int max) {
            if (str.length() == 2 * max) { // 左括号数目 + 右括号数目 = 2 * n
                res.add(str);
                return;
            }

            if (left < max) { // 左右括号都不能超过max
                backtrace(res, str + "(", left + 1, right, max);
            }
            if (left > right) { // 左一定大于右，即右一定不能大于左，否则会出现：")("的情况
                backtrace(res, str + ")", left, right + 1, max);
            }
        }

        // 回溯的第二种写法
        public static void backtrace(String sublist, List<String> res, int leftNum, int rightNum) {
            if (leftNum == 0 && rightNum == 0) { // 左右括号都已经用完
                res.add(sublist);
                return;
            }

            if (leftNum > rightNum) // 比如 ())....肯定不会是匹配的括号，直接返回(剪枝)
                return;

            if (leftNum > 0) // 还有左括号可以用
                backtrace(sublist + "(", res, leftNum - 1, rightNum);

            if (rightNum > 0) // 还有有括号可以用
                backtrace(sublist + ")", res, leftNum, rightNum - 1);
        }
    }
}
